package experiment3.shudu001.models;

import java.util.Random;

/**
 * Created by HP on 2025/4/26.
 */


public class SudokuGenerator {

    private static final int SIZE = 9;
    private static final int EMPTY = 0;
    private Random random = new Random();

    public int[][] generate(int difficulty) {
        int[][] board = new int[SIZE][SIZE];

        // 生成完整解
        solve(board);

        // 根据难度移除数字
        int cellsToRemove = 0;
        switch (difficulty) {
            case 1: cellsToRemove = 10; break; // 简单
            case 2: cellsToRemove = 35; break; // 中等
            case 3: cellsToRemove = 45; break; // 困难
        }

        removeNumbers(board, cellsToRemove);
        return board;
    }

    private boolean solve(int[][] board) {
        for (int row = 0; row < SIZE; row++) {
            for (int col = 0; col < SIZE; col++) {
                if (board[row][col] == EMPTY) {
                    // 随机尝试数字
                    int[] numbers = {1, 2, 3, 4, 5, 6, 7, 8, 9};
                    shuffleArray(numbers);

                    for (int number : numbers) {
                        if (isValid(board, row, col, number)) {
                            board[row][col] = number;

                            if (solve(board)) {
                                return true;
                            } else {
                                board[row][col] = EMPTY;
                            }
                        }
                    }
                    return false;
                }
            }
        }
        return true;
    }

    private boolean isValid(int[][] board, int row, int col, int number) {
        // 检查行
        for (int c = 0; c < SIZE; c++) {
            if (board[row][c] == number) return false;
        }

        // 检查列
        for (int r = 0; r < SIZE; r++) {
            if (board[r][col] == number) return false;
        }

        // 检查3x3方块
        int boxRow = row / 3 * 3;
        int boxCol = col / 3 * 3;
        for (int r = boxRow; r < boxRow + 3; r++) {
            for (int c = boxCol; c < boxCol + 3; c++) {
                if (board[r][c] == number) return false;
            }
        }

        return true;
    }

    private void removeNumbers(int[][] board, int cellsToRemove) {
        int cellsRemoved = 0;
        while (cellsRemoved < cellsToRemove) {
            int row = random.nextInt(SIZE);
            int col = random.nextInt(SIZE);

            if (board[row][col] != EMPTY) {
                int temp = board[row][col];
                board[row][col] = EMPTY;

                // 确保解唯一
                int[][] tempBoard = copyBoard(board);
                SudokuSolver solver = new SudokuSolver();
                if (solver.countSolutions(tempBoard) == 1) {
                    cellsRemoved++;
                } else {
                    board[row][col] = temp;
                }
            }
        }
    }

    private int[][] copyBoard(int[][] board) {
        int[][] copy = new int[SIZE][SIZE];
        for (int row = 0; row < SIZE; row++) {
            System.arraycopy(board[row], 0, copy[row], 0, SIZE);
        }
        return copy;
    }

    private void shuffleArray(int[] array) {
        for (int i = array.length - 1; i > 0; i--) {
            int index = random.nextInt(i + 1);
            int temp = array[index];
            array[index] = array[i];
            array[i] = temp;
        }
    }
}